package com.thoughtworks.trains;

import java.util.Arrays;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * 
 * @author water
 *
 */
public class Town {
	
	//站名
	private String name;
	//可达站点
	private Town[] routes;
	//保存其他站点可达当前站点的信息和可达的距离信息（被可达）
	private Distance[] dis;
	//统计可达站点的数量
	private transient AtomicInteger routeCount = new AtomicInteger();
	//统计被可达站点的数量
	private transient AtomicInteger disCount = new AtomicInteger();
	
	private static int DEFAULT_SIZE = 16;
	
	private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
	
	/**
	 * 
	 * @param name 站名
	 */
	public Town(String name){
		this.name = name;
		routes = new Town[DEFAULT_SIZE];
		dis = new Distance[DEFAULT_SIZE];
	}
	
	/**
	 * 
	 * @param name 站名
	 * @param size 可达站点/可达站点的数量，可自动扩容
	 */
	public Town(String name, int size){
		if(size <= 0 ){
			size = DEFAULT_SIZE;
		}
		this.name = name;
		routes = new Town[size];
		dis = new Distance[size];
	}
	
	/**
	 * 添加可达当前站点的站点，以及距离
	 * @param start  起点站
	 * @param distance  起点站到当前站的距离
	 * @return
	 */
	public boolean addRouteFromStartTown(Town start, int distance){
		if(distance <= 0){
			throw new IllegalArgumentException("distance should be more than 0");
		}
		Distance newDis = new Distance(start,distance);
		if(isDisArrayFull()){
			resizeDistanceArray();
		}
		dis[disCount.getAndIncrement()] = newDis;
		return true;
	}

	/**
	 * 添加当前站点可达的站点
	 * @param reachableTown 可达站点
	 * @return
	 */
	public boolean addReachableTown(Town reachableTown){
		if(reachableTown == null){
			throw new NullPointerException("Town object should not be null");
		}
		if(isReachableTownFull()){
			resizeReachableTownArray();
		}
		
		routes[routeCount.getAndIncrement()] = reachableTown;
		
		return false;
	}
	
	@Override
	public int hashCode() {
		return name.hashCode();
	}
	
	@Override
	public boolean equals(Object obj) {
		if(obj instanceof Town){
			Town town = (Town)obj;
			return this.name.equalsIgnoreCase(town.getName());
		}else{
			return false;
		}
	}
	
	/**
	 * 返回当前站点可达的站点
	 * @return
	 */
	public Town[] getRoutes(){
		return routes;
	}
	
	public Town getReachableTownByName(String name){
		for(int i=0; i<routeCount.get(); i++){
			Town existed = routes[i];
			if(existed.getName().equalsIgnoreCase(name)){
				return existed;
			}
		}
		throw new IllegalArgumentException("don't have this town : "+name);
	}
	
	private boolean isDisArrayFull() {
		return disCount.get() == dis.length;
	}

	/**
	 * 扩容dis数组
	 */
	private void resizeDistanceArray() {
		
		int minCapacity = dis.length+1;
		int oldCapacity = dis.length;
		int newCapacity = resize(minCapacity,oldCapacity);
		
		dis = Arrays.copyOf(dis, newCapacity);
	}
	
	
	/**
	 * 扩容routes数组
	 */
	private void resizeReachableTownArray() {
		
		int minCapacity = routes.length+1;
		int oldCapacity = routes.length;
		int newCapacity = resize(minCapacity,oldCapacity);
		
		routes = Arrays.copyOf(routes, newCapacity);
	}

	/**
	 * 50%扩容
	 * @param minCapacity
	 * @param oldCapacity
	 * @return
	 */
	private int resize(int minCapacity,int oldCapacity){
		int newCapacity = oldCapacity + (oldCapacity >> 1);
		if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
		if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
		return newCapacity;
	}
	
	private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0)
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

	private boolean isReachableTownFull() {
		return routeCount.get() == routes.length ;
	}

	public String getName() {
		return name;
	}

	public int getDis(Town town) {
		for(int i = 0 ; i< disCount.get() ; i++){
			Distance one = dis[i];
			if(one.getStart().equals(town)){
				return one.getDistance();
			}
		}
		return 0;
	}

	/**
	 * 查询路线,递归问题
	 * @param endTown
	 * @param stops
	 * @return
	 */
	public int search(Town endTown, int stops) {
		
		if(stops == 0){
			return 0;
		}
		int trips = 0;
		for(int i=0; i< routeCount.get() ; i++){
			Town next = routes[i];
			if(next.equals(endTown)){
				trips++;
				trips+=next.search(endTown,stops-1);
			}else{
				trips+=next.search(endTown,stops-1);
			}
			
		}
		
		return trips;
	}
	
}

class Distance {
	private Town start;
	private int distance;
	
	public Distance(Town start, int dis){
		this.start = start;
		this.distance = dis;
	}


	@Override
	public int hashCode() {
		return start.hashCode();
	}

	public Town getStart() {
		return start;
	}

	public int getDistance() {
		return distance;
	}
	
}
